翻訳と辞書
Words near each other
・ Closer to the Truth (Cher album)
・ Closer to the Truth (Tony Joe White album)
・ Closer to Truth
・ Closer to You
・ Closer to You (Carried Away album)
・ Closer to You (JJ Cale album)
・ Closer to You (The Coronas album)
・ Closer to Your Heart
・ Closer to Your Heart (Clannad song)
・ Closer to Your Heart (Natalie Grant song)
・ Closer/Sweet Dreams
・ Closers
・ Closest pair of points problem
・ Closest point method
・ Closest point problem
Closest string
・ Closest Thing to Heaven
・ Closest Thing to Heaven (album)
・ Closet
・ Closet (disambiguation)
・ Closet Cases of the Nerd Kind
・ Closet Children
・ Closet drama
・ Closet flange
・ Closet Land
・ Closet Monster
・ Closet Monster (film)
・ Closet screenplay
・ Closet Space
・ Closet? You'll Love It!


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Closest string : ウィキペディア英語版
Closest string
In theoretical computer science, closest string is the name of an NP-hard computational problem, which tries to find the geometrical center of a set of input strings.
To understand the word "center" it is necessary to define a distance between two strings. Usually, this problem is studied with the Hamming distance in mind.
==Formal definition==
More formally, given ''n'' length-''m'' strings ''s''1, ''s''2, ..., ''s''''n'', the closest string problem seeks for a new length-''m'' string ''s'' such that ''d''(''s'',''s''''i'') ≤ ''k'' for all ''i'', where ''d'' denotes the Hamming distance, and where ''k'' is as small as possible. A decision problem version of the closest string problem, which is NP-complete, instead takes ''k'' as another input and asks for any string that is within Hamming distance ''k'' of all the input strings.〔
The closest string problem can be seen as an instance of the 1-center problem in which the distances between elements are measured using Hamming distance.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Closest string」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.